package com.example.demo.leetcode.zuocheng.graph;

import java.util.ArrayList;

/**
 *  给定一个N*N的棋盘，其中存放N个棋子，要求每个棋子不共行，共列，共斜线，问有多少种方法
 *  思路:
 *       入参: record
 *             i 表示当前多少行
 *             n  表示一共多少行
 *       结束条件, n==i return 1; 一种可能
 *      从第一行开始遍历，每个可能的位置存放在数组record中, record[5]=6 标识坐标(5,6)
 *      其中遍历到每到一行,所有列  的可能性跟下一层的结果递归累加.
 *      判断可能性的方法: 如果 纵坐标想等 或者 (横坐标-横坐标) == (纵坐标-纵坐标) 返回false
 *
 * @author xujm
 * @version V2.4
 * @since 2.4.0 2021/7/11 15:38
 */
public class Arr_N皇后问题 {



    public static int process(int [] record, int i , int n){

        if(n == i){
            return 1;
        }

        //遍历列
        int res=0;
        for(int j=0;j<n;j++){
            if(isValid(record,i,j)){
                record[i] = j; //记录一个节点
                res += process(record,i+1,n); //累加下一个递归
            }
        }
        return res;
    }

    public static boolean isValid(int [] record, int i , int j){

        //遍历历史有行 校验是否不符合
        for(int k=0;k<i;k++){
            if(record[k] == j || Math.abs(i-k)==Math.abs(j - record[k])){
                return false;
            }
        }
        return true;
    }


    //位运算 实现N皇后问题 0<n<=32
    public static int num2(int n){

        int limit = n == 32 ? -1 : (1 << n)-1;
        return processWei(limit,0,0,0);
    }

    /**
     *
     * @param limit 如果是8 皇后  11111111
     * @param colLimit  列限制
     * @param leftDiaLimit 左斜线 限制位   通过 左斜线<<1 得到
     * @param rightDiaLimit 右斜线 限制为 通过 右斜线>>>1 得到
     * @return
     */
    public static int processWei(int limit , int colLimit , int leftDiaLimit , int rightDiaLimit){

        //列限制塞满，表示n个皇后全部塞入了 结束返回1
        if(limit == colLimit){
            return 1;
        }
        //定义pos 获取所有可以存放皇后的位置
        //遍历pos，每次获取最右边的1作为皇后的位置作为遍量 mostRightOne
        //累加下次递归，根据mostRightOne结算入参
        int pos = limit & (~(colLimit | leftDiaLimit | rightDiaLimit));
        int mostRightOne = 0;
        int res = 0;
        while (pos != 0){
            mostRightOne = pos &(~pos + 1);
            pos = pos - mostRightOne;
            res += processWei(limit,colLimit | mostRightOne, (leftDiaLimit | mostRightOne)<<1,(rightDiaLimit | mostRightOne)>>1);
        }
        return res;
    }


    public static void main(String[] args) {
        int n =10;
        int [] arr = new int[n];

        long start = System.currentTimeMillis();
        int process = process(arr, 0, n);
        long end = System.currentTimeMillis();
        System.out.println(end - start);
        System.out.println(process);
        start = System.currentTimeMillis();
        int process2 = num2(n);
        end = System.currentTimeMillis();
        System.out.println(end - start);
        System.out.println(process2);

    }





}
